package demo.practice.leetcode_base;

import java.util.*;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class P103 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        P103 p103 = new P103();
        p103.zigzagLevelOrder(root);

    }

    /**
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * <p>
     * 3  进栈  出栈   [3]
     * 20进栈  9进栈
     * 9出栈   [9,
     * 20出栈  [9,20]
     * 7栈 15进栈
     * 15出栈 [15,
     * 7出栈  [15,7]
     * <p>
     * <p>
     * [3]
     * [9,20]
     * [15,7]
     */

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        TreeNode current = root;
        List<List<Integer>> l = new ArrayList<>();
        if (root == null)
            return l;
        List<TreeNode> q = new ArrayList<>();
        q.add(root);
        int i = 0;
        while (q.size() > 0) {
            List<TreeNode> st2 = new ArrayList<>();
            List<Integer> ll = new ArrayList<>();
            int len = q.size();
            for (int j = 0; j < len; j++) {
                TreeNode node = q.get(j);
                if (i % 2 == 0)
                    ll.add(node.val);
                else
                    ll.add(0, node.val);

                if (node.left != null) {
                    st2.add(node.left);
                }
                if (node.right != null) {
                    st2.add(node.right);
                }
            }
            l.add(ll);
            q = st2;
            i++;
        }
        return l;
    }
}
